package 差分Plus离散化;

import org.junit.Test;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class lc周赛花期内花的数目 {
	@Test
	public void test() {
		int arr[] = {1,3,4,6,6,14,23,88};
		System.out.println(Arrays.binarySearch(arr, 6));
		System.out.println(getLeft(arr,6));
		System.out.println(getLeftIndex(arr,6));
		System.out.println(getRight(arr,99));
	}
	@Test
	public void testForResult() {
//		int f[][] = {{19,37},{19,38},{19,35}};
//			int per[]	 = {6,7,21,1,13,37,5,37,46,43};
			int f[][] = {{1,6},{3,7},{9,12},{4,13}};
			int per[]	 = {2,3,7,11};
		System.out.println(Arrays.toString(solutionOne(f,per)));
//		System.out.println(Arrays.toString(fullBloomFlowers(f,per)));
	}
	
	public static void main(String []args) {
		
		
		
		int f [][] = {{1,10},{3,3},{2,2}};
		int per [] = {3,3,2};
		Arrays.sort(f,new Comparator<int []>() {
			@Override
			public int compare(int[] o1, int [] o2) {
				return o1[0] - o2[0];
//				return 0;
			}
			
		});
		for(int []arr : f)
			System.out.println(Arrays.toString(arr));		
		Arrays.sort(f,(o,p) -> (p[0] - o[0]));
//		System.out.println(Arrays.toString(f));
		for(int []arr : f)
			System.out.println(Arrays.toString(arr));
		System.out.println(Arrays.toString(solution(f,per)));
	}
	/**
	 * 
	 *下面的 方法 是纯暴力的 行为  超时 显而易见
	 * 时间复杂度 O（n * k ）；
	 * n 是人的 个数 k 是 二维数组的 长度 其实 真实的复杂度 应该是 O(n * k * 2)
	 * 最后 这个 2  表示的 是 二维数组 中 一维 数组的 长度
	 * 
	 * @param flowers
	 * @param persons
	 * @return
	 */
	public static int [] solution(int [][]flowers,int persons[]) {
		int len = persons.length;
		int ans[] = new int [len];
		Arrays.sort(persons);
		for(int j = 0; j < len ;j++) {
			if(j > 0 && persons[j] == persons[j - 1] ) {
				ans[j] = ans[j - 1];
				continue;
			}
			for(int i = 0; i < flowers.length;i++) {
				if(persons[j]<= flowers[i][1] && persons[j] >= flowers[i][0]) {
					ans[j]++;
				}
			}
			
		}
			
		
		return ans;
	}
	/**
	 * //		int a [] = {3,4,4,1,2,0};
		Integer a [] = {3,4,4,1,2,0};
		Arrays.sort(a,(i,j) -> (i  - j));
		ArrayList<int []>  list= new ArrayList<>(); 
	 * 这个题  还学到了 一些 java的 基础知识   数组 也是 引用数据类型 
	 * Arrays.sort(flowers, (o, p) -> o[0] - p[0]);
	 * 
	 * 上面这 样写 与 下面 这样 写是 完全 等效的   Lambda 表达式 ( 这还没有 涉及到       函数 引用)
	 *      注意 排序 中的 规则 问题 返回   正数 表示 升序 负数 表示 降序   返回  0   表示   顺序 不变
	 * 		Arrays.sort(f,new Comparator<int []>() {
			@Override
			public int compare(int[] o1, int [] o2) {
				return o1[0] - o2[0];
//				return 1;
			}
			
		});
	 * 
	 * 牛逼 plus
	 * 
	 */
	
	/**
	 * 在暴力的   基础上 做了 一点 优化 
	 * 明白 这个 的 整个 过程  是 怎样做到的 
	 * pt 表示当前 人 来时的 time
	 * st 表示 花的 开始 时间 
	 * et 表示 花的 凋谢 时间
	 * 
	 *  整体的 思路 就是 :
	 *  当前 pt 能看 的 花 开的情况有 
	 *  ① : st == pt(正开)  此时 必能 看 到
	 *  	
	 *  			  ① et < pt  这个 时候 花 已经凋谢 了 看不到  ×
	 *  ②   st < pt(已经开)
	 *  			  ② et >= pt 这个时候  花 还没有凋谢 ,也能看到  √ 
	 * 所以 每个人的 看到的 花 开的 数目 就是  ① + ②.②  
	 * 这样的  话 就可以产生 两种 计算的 方法 
	 * 一 :  ① + ② - ②.①
	 二:   ① + ②.② 
 	 */
	// Arignote 的  写法   88 ms 左右 虽然抽象,但是  却很秒!
	public int[] fullBloomFlowers(int[][] flowers, int[] persons) {
		PriorityQueue<Integer> queue = new PriorityQueue<>();
		Arrays.sort(flowers, (o, p) -> o[0] - p[0]);
		Integer[] index = new Integer[persons.length];
		for (int i = 0; i < persons.length; i++) {
			index[i] = i;
		}
//		Runnable
//		new Thread(()->{
//			System.out.println();
//		}).start(); 
//		
		
		Arrays.sort(index, (o, p) -> persons[o] - persons[p]);
		/**
		 * 这个 排序 真的 就很抽象 卧槽 
		 * 超乎 想象的  排序 规则 
		 */
		int[] result = new int[persons.length];
		for (int i = 0, j = 0; i < persons.length; i++) {
			for (; j < flowers.length && flowers[j][0] <= persons[index[i]]; j++) {
				queue.offer(flowers[j][1]);
			}
			while (!queue.isEmpty() && queue.peek() < persons[index[i]]) {
				queue.poll();
			}
			result[index[i]] = queue.size();
		}
		return result;
	}
	/**
	 * 对上面的  方法 进行 实现
	 *  但是 不 按 Arignote 的 实现的 话 需要  需要 手写 一个  二分 查找 (不是 普通的 二分查找) 
	 *
	 *效果确实  比 arignote的 快一些  28  ms 
	 */
	public static int [] solutionOne(int [][]flowers,int persons[]) {
		int len = persons.length;
		int flen = flowers.length;
		int ans [] = new int [len];
//		//先 按照 st 进行 排序  这种 实现 不了 还是  得 抽取 出 st 和 et 数组出来 
//		Arrays.sort(flowers,(o1,o2) -> (o1[0] - o2[0]));
		
		int st [] = new int [flen];
		int et [] = new int [flen];
		for(int i = 0;i < flen ;i++) {
			st[i] = flowers[i][0];
			et[i] = flowers[i][1];
		}
		Arrays.sort(st);
		Arrays.sort(et);
		int temp = 0;
		for(int i = 0; i < persons.length;i++) {
//			 temp = getRight(st,persons[i]) + 1;
			 ans[i] = getRight(st,persons[i]) + 1;
//   下面的 逻辑是有问题的 			 
//			 temp -= getLeft(et,persons[i]);
//			 ans[i] -= getLeft(et,persons[i]);
			 temp  = getLeft(et,persons[i]);
			 /**
			  * 这里 还有一个 小的细节 在这里 
			  *  卧槽 
			  *  		f[][] = {{19,37},{19,38},{19,35}};
		            per[]{6,7,21,1,13,37,5,37,46,43};
		            这个 测试样例 就很秒 
			  */
			 ans[i] = temp == -1 ? 0 : ans[i] - temp;
//			 ans[i] = temp; 
		}
		
/**
 * 		Arrays.binarySearch(a, key)
 	不能用 Java 自带  的 二分 查找  这只是 普通的 一个 二分 查找 没有啥 特别的 功能
 */
		return ans;
	}
	
	/**
	 * 这他妈 是 真的 绕 
	 * 
	 * 这里 做一个 统一  :
	 * 让 arr[mid] op target 这样的 一个 运算顺序 这样 不容易 迷 
	 * if arr[mid] >= target 那么 就是 在 数组 中 找到   >= target 的 最左侧的 索引
	 * if arr[mid] <= target 就是 在数组中 找到   <= target 的最  右侧 的位置
	 */
	
	public static int getLeft(int arr[] ,int target) {
		int ans = -1;
		int r = arr.length - 1;
		int l = 0;
		while(l <= r) {
			int mid = l + r >> 1;
			if(arr[mid] >= target) {
				ans = mid;
				r = mid - 1;
			}
			else
			  l = mid  + 1;
		}
		return ans;
	}
	
	public static int getRight(int arr[] ,int target) {
		int ans = -1;
		int r = arr.length - 1;
		int l = 0;
		while(l <= r) {
			int mid = l + r >>1;
			if(arr[mid] <= target) {
				ans = mid;
				l = mid +1;
			}
			else
				r = mid - 1;
		}
		return ans;
	}
	
	public static int getLeftIndex(int nums[],int value) {
		/**
		 * 用这个 index 记录着 并更新 这个  满足条件的 最左侧的下标
		 * 可以 省去 
		 * 但是 没必要 
		 * 就算 多用  这一个  int 的变量 又不会 死 干嘛 写的 那么  去 扣 coding 的 简洁
		 */
		int index = -1;
		int l = 0 ;
		int r = nums.length - 1;
		int mid = 0;
		while(l <= r) {
			mid = l + ((r - l )>>1);
			/**
			 * 这里 做个 解释   
			 * int arr []= {5,7,7,8,8,10};
			 * value  = 7
			 * 对于上面 的   数组 来说 
			 * 条件是 nums[mid] >= value 时候返回的 是   index 是 1
			 * 而条件 是   nums[mid] > value 的时候 返回的 结果 是 index 是 3
			 * 这就不需要 我多解释了 吧 
			 */
			if(nums[mid] > value) {
				index = mid;
				r = mid -1;
			}
			else {
				l  = mid + 1;
			}
		}
		return index;
	}

}
